An undirected graph has 5 nodes. What is the greatest number of edges it can have?

A directed graph has 10 edges. What is the smallest number of nodes it can have?

An undirected graph with 20 nodes and 30 edges has three connected components: \(A\), \(B\), and \(C\). Connected component \(A\) has 7 nodes. What is the smallest number of edges it can have?

Let \(v = \{a, b, c, d, e, f, g\}\) and \(E = \{(a,g), (b,d), (d, e), (f, d)\}\). How many connected components does the undirected graph \(G =(V, E)\) have?

Let \(G = (V, E)\) be a directed graph with \(|V| > 1\). Suppose that every node in \(G\) is reachable from every other node. True or False: each node in the graph must have an out-degree of at least one and an in-degree of at least one.

An undirected graph \(G = (V, E)\) has 23 nodes and 2 connected components. What is the smallest number of edges it can have?

Let \(G = (V, E)\) be an undirected graph, and suppose that \(u, v, \) and \(w\) are three nodes in \(V\). Suppose that \(u\) and \(v\) are in the same connected component, but \(u\) and \(w\) are not in the same connected component. True or False: it is possible that \(v\) and \(w\) are in the same connected component.

Let \(G\) be an undirected graph. Suppose that the degree of every node in the graph is greater than or equal to one. True or False: \(G\) must be connected.

What is the out-degree of node \(u\) in the graph shown below?

Suppose \(u\) is a node in a complete, undirected graph \(G = (V,E)\). What is the degree of \(u\)? Remember, an undirected graph is complete if it contains every possible edge.

Let \(V = \{a, b, c, d\}\) and \(E = \{(a,b), (a,a), (a,c), (d,b), (c,a)\}\) be the nodes and edges of a directed graph. How many predecessors does node \(b\) have?

Let \(C\) be a connected component in an undirected graph \(G\). Suppose \(u_1\) is a node in \(C\) and let \(u_2\) be a node that is reachable from \(u_1\). True or False: \(u_2\) must also be in the same connected component, \(C\).

Let \(G = (V, E)\) be a connected, undirected graph with 16 nodes and 35 edges. What is the greatest possible number of edges that can be in a simple path within \(G\)?

Suppose \(G = (V, E)\) is an undirected graph. Let \(k\) be the number of connected components in \(G\). True or False: it is possible that \(k > |E|\).

Let \(G = (V, E)\) be a directed graph, and suppose \(u, v, w \in V\) are all nodes. True or False: if \(w\) is reachable from \(v\), and \(v\) is reachable from \(u\), then \(w\) is reachable from \(u\).

Let \(G = (V,E)\) be a connected, undirected graph with \(|E| = |V| - 1\). Suppose \(u\) and \(v\) are both nodes in \(G\). True or False: there can be more than one simple path from \(u\) to \(v\).

Suppose an undirected graph \(G = (V,E)\) has two connected components, \(C_1\) and \(C_2\). Suppose that \(|C_1| = 4\) and \(|C_2| = 3\). What is the largest that \(|E|\) can possibly be?

Suppose an undirected graph has 16 edges. What is the smallest number of nodes it can have?

7 Show Answer

Suppose a directed graph has 5 nodes and 3 edges. What is the greatest possible degree of any node in the graph?

4 Show Answer

The adjacency matrix of a directed graph with nodes \(u_1, \ldots, u_8\) is shown below:

True or False: there is a path from node \(u_1\) to node \(u_8\).

Let \(G = (V, E)\) be a directed graph with the property that there is a node \(u\) in \(G\) such that every other node in \(G\) is reachable from \(u\).

Let \(H \) be the directed graph obtained from \(G\) by reversing the direction of every edge. True or False: there must be a node \(v\) in \(H\) such that every other node in \(H\) is reachable from \(v\).

Suppose an undirected, connected graph has \(n\) nodes, half of which are colored red and the other half are colored blue. Each red node is neighbors with \(n/4\) blue nodes, and each blue node is neighbors with \(n/4\) red nodes. There are no edges between nodes of the same color.

What is the time complexity of computing a shortest path from a given red node to all other red nodes using BFS?

Let \(G = (V, E)\) be a connected, undirected graph with \(|E| = |V| - 1\). Suppose \(u\) and \(v\) are two nodes in \(V\).

True or False: there can be two different simple paths from \(u\) to \(v\) in \(G\).

Let \(G=(V,E)\) be an undirected graph with \(V=\{a,b,c,d,e\}\) and \(E=\{(a,b),(c,d),(e,a),(b,c),(e,d),(d,a)\}\).

True or False: it is possible to color nodes of \(G\) with red and blue such that there are no edges between nodes of the same color.

A ``hub node'' in a graph is a node that has an edge to all the other nodes in the graph.

What is the worst case time complexity of an efficient algorithm that checks to see if a graph \(G = (V,E)\) has a hub node? You should assume that the graph is represented as an adjacency list. State your answer in asymptotic notation and in terms of \(V\) and \(E\).

Note: in studying, you might have come across a problem in the practice bank about ``hub and spoke'' graphs. This question is related, but not the same!

\(\Theta(V)\) Show Answer